package 回溯;

public class Queen {
	
	private int[] queen;	// 记录皇后摆放的位置. 索引是行, 值是列
	private int ways;	// 记录摆法
	
	public static void main(String[] args) {
		new Queen().placeNQueen(4);
	}
	
	public void placeNQueen(int n) {
		if (n < 1) return;
		queen = new int[n];
		place(0);
		
	}
	
	public void place(int row) {
		if (row == queen.length) {
			ways++;
			show();
			return;
		}
		for (int col = 0; col < queen.length; col++) {
			if (isValid(row, col)) {
				queen[row] = col;	// 摆放皇后
				place(row + 1);	// 进行下一行的摆放
			}
		}
	}
	
	/**
	 * 判断第row行第col列的摆放位置是否合法
	 * @param row
	 * @param col
	 * @return
	 */
	public boolean isValid(int row, int col) {
		for (int i = 0; i < row; i++) {
			if (queen[i] == col) return false;
			if (row - i == Math.abs(col - queen[i])) return false;
		}
		return true;
	}
	
	public void show() {
		for (int row = 0; row < queen.length; row++) {
			for (int col = 0; col < queen.length; col++) {
				if (queen[row] == col) {
					System.out.print("1 ");
				} else {
					System.out.print("0 ");
				}
			}
			System.out.println();
		}
		System.out.println(ways);
	}
}
